The present invention relates to an LDPC check matrix generation method, check matrix generator, and code retransmission method, and more particularly to an LDPC check matrix generation method, check matrix generator and code retransmission method, by which when two LDPC systematic codes having different encoding ratio in a rate-compatible relationship are C0 and C1, and the information bit sizes of the codes C0 and C1 are both K, and the parity bit sizes thereof are M0 and M1 (M0<M1) respectively, the check matrix H1 or H0 of one code, C1 or C0, is generated from the check matrix H0 or H1 of the other code C0 or C1.
Systematic Code and Block Code
In general, encoding using an information alphabets having q number of different values (q=2 in a case of bits) is performed, as shown tin FIG. 13, by making a block I1 having K number of information alphabets, correspond with a block I2 having N number (N>K) of code alphabets (code bits) on a one-to-one basis. Hereafter the term “bit” is used instead of “alphabet”.
In this case, a code, when K bits out of N number of bits of the block I2 are constituted by the information bits of the block I1, is called a “systematic code”. The remaining M=N−K bits are called “parity bits”, and are acquired by performing a predetermined processing, such as addition, on the information bits.
In other words, a code, when K bits out of the N bits which constitutes the code are the information bits, and the remaining M (=N−K) bits are the parity bits for error detection and correction, is called a “block code”, and a block code, when the first K bits of the code are the information bits and (N−K) bits of the parity bits comes after these K bits, is called a “systematic code”.
At the transmission side, if N number of code bitsx=(x0, x1, . . . , xN−1)are generated by the following expressionx=uG  (a)using the K×N generator matrixG=(gij);i=0, . . . , K−1;j=0, . . . , N−1for the K number of information bits u=(u0, u1, . . . , uK−1), then these code bits become block code, and the information bits u are block-encoded. If x is a systematic code, for example, then the generator matrix G can be expressed mathematically, as shown in FIG. 14.
At the reception side, the information bits u are estimated from the code vector x, which is the received data. For this, the information bits u are estimated so as to satisfy the following parity check relational expressionxHT=0  (b)with respect to x.
HereH=(hij);i=0, . . . , M−1;j=0, . . . , N−1is a parity check matrix, where HT is a transposition of H (replacement of row and column), and H and G satisfy the following relationship based on (a) and (b).GHT=0  (c)
This means that an encoding rule is uniquely determined if either H or G is provided. For example, if x is a systematic code and the generator matrix G is a matrix shown in FIG. 14, then the parity check matrix H can be expressed as shown in FIG. 15.
FIG. 16 is a block diagram depicting a communication system where block encoding is performed in a transmitter and the data is decoded in a receiver, and the transmitter 1 comprises an encoding unit 1a for encoding K bits of information u and generating N bits of block codes x, and a modulation unit 1b for modulating the block codes and transmitting the result. The receiver 2 comprises a demodulation unit 2a for demodulating the signal received via a transmission line 3, and a decoding unit 2b for decoding the originally transmitted K bits of information u from the N bits of received information.
The encoding unit 1a has a parity generator 1c for generating M (=N−K) number of parity bits p and a P/S conversion unit 1d for combining K bits of information u and M bits of parity bits p, and outputting N (=K+M) number of block codes x. Mathematically the encoding unit 1a outputs a block code x according to Expression (a). The decoding unit 2b has a decoder 2c for performing error detection correction processing on the received likelihood data y, and decoding the originally transmitted K bits of information, and outputting the estimated information. The block code x sent from the transmitter 1 is not input to the decoder 2c in a state immediately after being transmitted and influenced by the transmission line 3, but is input to the decoder 2c as likelihood data. The likelihood data is comprised of a reliability indicating whether a code bit is 0 or 1, and a sign (0 if level is +1, and 1 if level is −1). The decoder 2c performs a predetermined decoding processing based on the likelihood data for each code bit using the parity check relational expression in Expression (b), and estimates the information bits u.
LDPC Code
LDPC code (Low-Density Parity-Check code) is a generic term for codes defined by a check matrix H, where the ratio of the number of elements which are not 0 in the block code (number of is if q=2) to the total number of elements is low.
In particular, the code, when the number of elements which is not 0 (number of is) is constant in the rows and columns of the check matrix H respectively is called a “regular LDPC code”, and is characterized by the code length N, and the weight numbers (wc, wr) which are the number of elements of a column and row respectively. A type of code which allows different weight numbers in each column and each row of the check matrix H is called an “irregular LDPC code”, and is characterized by the code length N and the weight number distribution of a column and row ((λj, ρk); j=1, . . . , jmax; k=1, . . . , kmax). Here λj indicates a ratio of the number of elements that are different from 0 (number of 1s) and that belong to all the columns of which weight number is j to the entire number of elements that are different from 0. FIG. 17 is a diagram depicting the weight number distribution, and if the number of columns where the number of 1s is j is Nj in the M×N check matrix H and the total number of is in the check matrix H is E, the weight number distribution λj isλj=j×Nj/E, and the ratio fj of the number of columns where the number of 1s is j to the entire number columns isfj=Nj/N. 
If j=3 and Nj=4, for example, then λ3=12/E and fj=4/N. ρk indicates the ratio of the number of elements which are different from 0 (number of 1s) and which belong to all the rows of which weight number is k to the entire number of elements which are different from 0 and can be defined in the same way as the case of λj. Regular LDPC code can be regarded as a special case of an irregular LDPC code.
In the LDPC code, a concrete check matrix cannot be uniquely determined by determining only a code length N and weight number distribution. In other words, there are many concrete “1” layout methods (layout method of non-zero elements that are different from “0”) that satisfy a predetermined weight number distribution, and each defines a different code. The code error rate characteristic depends on the weight number distribution and the concrete layout of “1s” in the check matrix which satisfies this weight number distribution. The circuit scale, processing time and processing volume of the encoder and decoder are basically influenced only by the weight number distribution.
A general LDPC code is defined by a check matrix which is used for decoding processing, and for the encoding processing, a generator matrix G is determined by the check matrix H, or a parity bit is sequentially determined using a triangular check matrix, and regardless the case a processing time is required.
IRA Code
FIG. 18 is a configuration example of an encoder for generating IRA (Irregular Repeat Accumulate) code, which is a kind of irregular LDPC code. A bit repeat unit 5a repeats each bit u0 to uK−1 of information bits u for a predetermined number of times to generate and output an bit string consisted of E number of bits. The number of times of repeat of each bit may be different, and this is provided by a distribution function fi.
An interleaver 5b rearranges the sequence of the bit string consisted of E number of bits by interleave processing, and a first operation unit 5c repeats the addition of a number of bits from the head of the bit string acquired by the interleave processing, and inputs the each addition result to a second operation unit 5d. In other words, if the output of the interleave ise01, e02, e03, . . . e0a e11, e12, e13, . . . e1a e21, e22, e23, . . . e2a . . .eM−1,1, eM−1,2, . . . eM−1,a and each addition result of “a” number of bits is regarded as a bit vector xi, the first operation unit 5c performs the following calculation,x0=e01+e02+e03+ . . . +e0a x1=e11+e12+e13+ . . . +e1a x2=e21+e22+e23+ . . . +e2a . . .xM−1=eM−1,1+eM−1,2+ . . . +eM−1,a and outputs the addition result. In the first operation unit 5c, ADD is an adder and DL is a delay unit which input the addition result to the adder, and also outputs the result to the second operation unit 5d at each “a” times of addition.
The second operation unit 5d adds the previous addition result xi−1 and addition result xi of this time, which are output from the first operation unit, and outputs the addition result each time as a result a code bit string consisted of M number of parity bits is output. In the second operation unit 5d, ADD is an adder and DL2 is a one clock time delay unit. If the code bit vector, which is output from the second operation unit 5d, is p=(p0, p1, p2, . . . , pM−1), then the following relational expression is established.p0=x0 pi=pi−1+xii=1, . . . , M−1  (1)
The IRA code consisted of c0 to cN−1 is created by arraying M number of code bits p0 to pM−1 which are regarded as M number of parity bits, in serial after the information bits u0 to uK−1. The IRA code C is a kind of irregular LDPC codes and is expressed by the following expression.c=(c0, . . . , cN−1)=(u0, . . . , uK−1,p0, . . . , pM−1)  (2)
The IRA codes specified by the check matrix H (see FIG. 19) can be interpreted as a code that is improved so that the encoding processing time completes in a linear time which is proportion to the code length (see document 1: H. Jin, A. Khandekar and R. McEliece: “Irregular Repeat-Accumulate Codes,” Proceedings of 2nd International Sym. on Turbo Codes and Related Topics, Brest, France, pp. 1-8, September 2000).
In other words, considering that a value of each variable is a binary, that is, considering that the addition of the same bit becomes zero (ex. 1+1=0, 0+0=0), the above mentioned Expression (1) can be transformed into the following expression.p0+x0=0pi+pi−1+xi=0i=1, . . . , M−1  (3)
Each xi is a result of adding a number of input information bits ui, so if this is substituted in Expression (3), then Expression (3) can be interpreted as a parity check relationship expression for the IRA code c=(c0, c1, . . . cN−1).
FIG. 19 is a check matrix H of the IRA code obtained by the parity check relational expression in Expression (3), and if N=K+M, this check matrix H is a M×N matrix comprised of M×K information bit portion H1 and M×M parity bit portion H2. The number of is (weight number) included in each row of the information bit portion H1 is a number of times of additions “a” in the first operation unit 5c, and the distribution of is depends on the number of times of repeats of each bit in the bit repeat unit 5a. In other words, a number of is in the first column is a number of repeats of the information bit u0 in the bit repeat unit 5a, a number of 1s in the second column is a number of repeats of the information bits u1 in the bit repeat unit 5a . . . , and a number of 1s in the Kth column is a number of repeats of the information bit uK−1 in the bit repeat unit 5a, and the distribution is determined by interleave.
If the check matrix H of the IRA code is provided where the code bit is expressed by c, then the parity check relational expression is given by the following expression.cH=0
If Expression (2) is substituted in this expression, the parity bit p0 can be determined, and then p1 (=p0+x1) can be determined using this parity bit p0, and then pi+1 (=pi+x1+1) can be determined using the parity bit pi in the same way, and pM−1 can be finally determined. By combining the determined parity bits p0 to pM−1 with the information bits u0 to uK−1 in series, the IRA code shown by Expression (2) can be generated. In other words, if the check matrix H of the IRA code is given, the parity bits p0 to pM−1 can be determined, and the IRA code, which is an LDPC code, can be generated. Therefore once the check matrix H of the IRA codes is provided, it is not necessary to determine generator matrix G.
Number of Times of Addition “a” and Distribution Function fi
The number of times of addition “a” and the distribution function fi which shows number of times of bit repeat are determined based on characteristics and circuit scale. Here the distribution function fi is a ratio of the number of columns where the number of 1s is i to the total number of columns, described in the section of the LDPC code, that is Ni/N.
As a method for optimizing the code characteristics when the code length is long, a Density Evolution (DE) method is known (see the document 1). According to the DE method, the value of “a” should be great as the encoding ratio is higher. In particular, if the number of parity bits becomes half, that is if the encoding ratio increases, the characteristics of the code becomes better if the value of “a” doubles, and if the number of parity bits becomes double, that is if the encoding ratio decreases, the characteristics of the code improve if the values of “a” becomes half.
Generalizing IRA Code (Cyclic Matrix Type IRA Code)
As FIG. 20 shows, a parity check matrix is composed using a z×z cyclic matrix P(j). “Ps” in the information bit portion H1 are all different cyclic matrices having a same size (z×z), where a number of times of right shift is j, but j is omitted in FIG. 20. For example, when z=5, the cyclic matrix P(0) of which number of times of right shift is 0 is a unit matrix, and the cyclic matrix P(1) of which number of times of 1-bit right shift is as follows.
                              P          ⁡                      (            1            )                          =                  [                                                    0                                            1                                            0                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            0                                            1                                            0                                                                    0                                            0                                            0                                            0                                            1                                                                    1                                            0                                            0                                            0                                            0                                              ]                                    (        4        )            A blank indicates the 0 matrix in z×z, and I of the parity bit portion H2 indicates a z×z unit matrix. The number of cyclic matrices included in the rows and columns of the check matrix H need not be constant, and an optimum number is selected, just like IRA code, depending on the density development method or by simulation.
In the parity bit portion H2, the cyclic matrix P′ having the idential shift number is placed at the top and bottom of the first column, and the unit matrix I is placed at appropriate locations, and a first unit matrix I with size z×z is placed in steps in all remaining columns, then a second unit matrix I is placed so that two unit matrices I come next to each other in each column.
The first advantage of constructing the parity check matrix H by the z×z cyclic matrix P(j) is that the matrix can be expressed easily even if the size of the parity check matrix H increases. The size of M of an M×N parity check matrix H is about 1000 in an actual example, but if a cyclic matrix with z=100 is used, the matrix can be expressed by 10 rows. The second advantage is that if the weight number of each row of the check matrix H is W, the parity check matrix H can be constructed by placing W number of cyclic matrices in each row so as not to be in a same arrangement. In the above description, a cyclic matrix of which weight number is 1 is used, but a cyclic matrix with a 2 or higher weight number may be used.
Rate—Compatible Code
As FIG. 21 shows, when a code word of code C0, of which encoding ratio is greater than code C1, is a part of a code word of C1, the codes C0 and C1 are in a rate compatible relationship (rate-compatible codes). For example, a code C1 and a punctured code C0 thereof, or a code C0 and a code C1 by repetition thereof, are in a rate-compatible relationship. The information bit sizes of the codes C0 and C1 are K respectively, and the parity bit sizes are M0 and M1 (M0<M1) respectively.
Rate—Compatible LDPC Code
As a prior art, a rate-compatible LDPC code has been proposed (see document 2: J. Li and K. R. Narayanan: “Rate-Compatible Low Density Parity Check Codes for Capacity-Approaching ARQ Schemes in Packet Data Communications,” Proceedings of International Conference on Communications, Internet and Information Technology (CIIT), US Virgin Islands, pp. 201-206, November 2002). FIG. 22 is a diagram depicting a check matrix of a rate-compatible LDPC code.
As (A) of FIG. 22 shows, a check matrix H0 of code C0, which becomes a reference, is created by parameters optimized by the above mentioned DE method. Then as (B) of FIG. 22 shows, the check matrix H1 of code C1 is expanded so that the check matrix H0 of code C0 is included in a part of this check matrix H1. In this case, if IRA code is used, the weight number of 1 must be determined so that the weight distribution of the information bit portion of the check matrix H1 becomes as close as possible to the optimum distribution determined for code C1 by the DE method.
As described in the section of IRA code, if the encoding ratio is decreased by increasing parities, the weight number “a” in the check matrix of IRA code must be a small value. Therefore the weight number of the extended portion is decreased, and for the parity bit portion, a step matrix with weight number 2 is generated based on the IRA code.
Puncturing
When a code C1 of which information length is K and code length is N1 is provided, the encoding ratio of the code C1 is R1=K/N1. If a code of which encoding ratio is greater than R1 is constructed using this code C1, puncturing is performed. In other words, as FIG. 23 shows, the transmitter removes N0 out of N1 number of code bits, and sends the code having a code length N (=N1−N0). Since the removed bit position is known, the receiver performs decoding processing by interpolating data so that each bit has equal probability, and estimates the code C1. In this puncturing, the encoding ratio becomes R=K/N (>R1). The puncturing can be applied to LDPC code.
Repetition
When a code C1, of which information length is K and code length is N1, is provided, and a code of which encoding ratio is smaller than R1 (=K/N1) is constructed using this code C1, repetition is performed. As FIG. 24 shows, in this repetition, the transmitter repeats some bits (not limited to parity) out of N1 number of code bits more than once so as to add the total N0 number of bits, and sends a code having an N (=N1+N0) number of bits. The receiver performs diversity combining for the data of the repeat alphabet (simplest way is a mere addition), and decodes code C1. The repetition can be applied to LDPC code.
Dummy Bit Insertion
The dummy bit insertion method is one method of generating a code with encoding ratio R′<R for a systematic code having N=K+M bits of which encoding ratio is R (=K/N) by adding M number of parity bits to K number of information bits.
According to the dummy bit insertion method, as FIG. 25 shows, the transmitter adds K0 number of dummy bits DB having a known pattern to K number of information bits IB to generate K1=K+K0 number of information bits, and generates a systematic code C1 having N1=K1+M number of bits by generating M number of parity bits PB using the K1 number of information bits. At transmission, the transmitter adds the generated M number of parity bits PB to the K number of information bits after K0 number of dummy bits are removed from the K1 number of information bits, and sends the result as a code. The receiver adds the known dummy bits DB to the received signal for decoding.
H-ARQ
H-ARQ stands for Hybrid-ARQ (Auto Repeat request). This is a method of combining two basic technologies for improving information bit transmission efficiency, that is error correction code (FEC) and automatic repeat request (ARQ). (A) of FIG. 26 is a block diagram of a transmitter of a transmission system having the H-ARQ method, and (B) of FIG. 26 is a block diagram of a receiver.
In the transmitter of (A) of FIG. 26, an encoding unit 6a encodes transmission data at a predetermined encoding ratio. A punctured encoding unit 6b achieves a required encoding ratio using a punctured code pattern, and a data modulation unit 6c performs data modulation, and transmits the data. Generally the data modulation methods that are available are QPSK, 16QAM and 64QAM. A signal demodulation unit of the receiver in (B) of FIG. 26 has a configuration to perform retransmission/combining after punctured decoding, a data demodulation unit 7a performs data demodulation according to a modulation method, a punctured decoding unit 7b performs punctured decoding according to the encoding ratio, using a punctured code pattern, and a retransmission/combining unit 7c combines a data previously received and stored and the receive data, if this receive data is retransmission data. By this, higher receive quality can be obtained. A turbo decoding unit 7d performs error correction decoding processing on the combined data. H-ARQ retransmission control is performed according to the following procedure.                (1) The transmitter encodes information bits.        (2) The code bits are sent.        (3) The receiver corrects errors. Processing ends if decoding is performed correctly.        (4) If decoding fails, the receive data is stored, and retransmission is requested to the transmitter.        (5) The transmitter retransmits the code bits transmitted in (2).        (6) The receiver combines the stored data and retransmitted data, and executes the decoding processing on the resulting data.        (7) The above procedure is repeated until a predetermined maximum number of times of retransmission.        
In the above H-ARQ retransmission control, a method for always sending all code bits at the initial transmission and retransmission is called type-I H-ARQ or Chase Combining (CC), and a method for sending only a part of the code bits at initial transmission or retransmission is called type-II H-ARQ or Incremental Redundancy (IR).
Problems
When two LDPC systematic codes having the encoding ratio R0 and R1 (R0>R1), which are in a rate-compatible relationship, are C0 and C1, and the check matrix H1 of code C1 is generated from the check matrix H0 of code C0 which is a reference, the check matrix H1 is conventionally generated such that the weight number in the extended portion of the information bit portion of the check matrix H1 becomes a small value (see FIG. 22). With this conventional check matrix generation method, however, it is difficult to make the weight distributions of the check matrix H0 and check matrix H1 after extension to be the optimum simultaneously. This difficulty generates similar in a case where the encoding ratio R0 is smaller than the encoding ratio R1 of code C1.
Also in the case of a conventional check matrix generation method, complicated processing is required to extend the check matrix, and a large size memory is required to hold the check matrix.
In the case of the retransmission control based on the IR method, puncturing is performed, but in the conventional check matrix generation method, codes obtained by applying puncturing are characteristically not the optimum.